\documentclass{article}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{graphicx} 
\usepackage[left=1cm,right=1cm,top=1cm,bottom=2cm]{geometry}
\title{NumPDE Homework 2}
\author{Jiang Zhou 3220101339 }
\date{2025/3/10}

\begin{document}

\maketitle
\section*{Exercise 9.5}
Due to the definition of the matrix norm, we get that:
\begin{align*}
    \|r\|_2=\|Ae\|_2 &\leq \|A\|_2\|e\|_2\\
    \|x\|_2=\|A^{-1}b\|_2&\leq \|A^{-1}\|_2\|b\|_2
\end{align*}
By dividing the top and the bottom, we can get the left inequality and right inequality.

\section*{Exercise 9.8}
By Definition 9.3, we know that the condition number of a matrix $A$ is 
\begin{align*}
    cond(A) := \|A\|_2\|A^{-1}\|_2.
\end{align*}
where $\|A\|_2 = |\max_{1\leq k \leq n-1}{\lambda_k(A)}|$ and $\|A^{-1}\|_2 = \frac{1}{|\min_{1\leq k \leq n-1}{\lambda_k(A)}|}.$\\
So we can compute $cond(A)$:
\begin{align*}
    cond(A) = \frac{\frac{4}{h^2}\sin^2(\frac{(n-1)h\pi}{2})}{\frac{4}{h^2}\sin^2(\frac{h\pi}{2})} = \frac{\sin^2(\frac{(n-1)\pi}{2n})}{\sin^2(\frac{\pi}{2n})} = \frac{\cos^2(\frac{\pi}{2n})}{\sin^2(\frac{\pi}{2n})}.
\end{align*}
When $n = 8$, \(cond(A)  \approx 25.27 \) .\\
When $n = 1024$, \(cond(A)\approx 4.15\times10^{5}\) 

\section*{Exercise 9.11}
As shown in Figure 1, the maximum wavenumber that is representable on $\Omega_h$ is \(k_{\text{max}} = \frac{1}{h}\).\\
When we require that the Fourier mode be zero at the boundary points $x = 0$ and $x=1$, we are effectively imposing Dirichlet boundary conditions. \(u(0) = 0, u(1) =0\)
\begin{figure}
    \centering
    \includegraphics[width=0.3\linewidth]{E9_11.jpg}
    \caption{Exercise 9.11}
    \label{E9_11}
\end{figure}
\section*{Exercise 9.14}
As shown in Figure 2:
\begin{figure}
    \centering
    \includegraphics[width=0.3\linewidth]{E9_14.jpg}
    \caption{Exercise 9.14}
    \label{E9_14}
\end{figure}
\section*{Exercise 9.17}
By Lemma 7.25, we can decompose the matrix $A$ orthogonally:
\begin{align*}
    A = Q \Lambda Q',    
\end{align*}
where $Q$ is a identity orthogonal matrix and \(\Lambda = \text{diag}\{\lambda_1,\lambda_2\dots \lambda_{n-1} \}\).\\
Then we apply the decomposition into $T_w$:
\begin{align*}
    T_w = I - \frac{wh^2}{2}A = QQ' - \frac{wh^2}{2}Q\Lambda Q' = Q(I - \frac{wh^2}{2}\Lambda)Q' = Q\Lambda_{T_w}Q'.
\end{align*}
where $\Lambda_{T_w}$ is the characteristic matrix of $T_w$.\\
\begin{align*}
    \Lambda_{T_w} = 
    \begin{bmatrix}
        1 - \frac{wh^2}{2}\lambda_1(A) & 0 &\dots& 0 \\
	0     & 1 - \frac{wh^2}{2}\lambda_2(A) &  &0 \\
        \vdots& &\ddots&\vdots\\
	0 & 0 & \dots&1 - \frac{wh^2}{2}\lambda_{n-1}(A)
    \end{bmatrix}
\end{align*}
So we can get \(\lambda_k(T_w) = 1 - \frac{wh^2}{2}\lambda_k(A) = 1 - \frac{wh^2}{2}\frac{4}{h^2}\sin^2(\frac{kh\pi}{2})= 1 - 2w\sin^2\frac{k\pi}{2n}\).

\section*{Exercise 9.18}
As shown in Figure 3:
\begin{figure}
    \centering
    \includegraphics[width=0.3\linewidth]{E9_18.jpg}
    \caption{Exercise 9.18}
    \label{E9_18}
\end{figure}

\section*{Exercise 9.21}
As shown in Figure 4:
\begin{figure}
    \centering
    \includegraphics[width=0.4\linewidth]{E9_21.jpg}
    \caption{Exercise 9.21}
    \label{E9_21}
\end{figure}


\section*{Exercise 9.35}
In a D-dimensional domain with \(n = 2^m\) cells \( ( m \in \mathbb{N}^{+} ) \) along each dimensional, the storage cost of FMG-cycles $C$ is:
\begin{align}
    C = 2n^D(1 + 2\times 2^{-D} + 3\times 2^{-2D} + \dots + (m + 1)\times 2^{-mD}) 
\end{align}
To compute the storage cost of FMG-cycles $C$, we can multiply $(1)$ by $2^{-D}$:
\begin{align}
    2^{-D}C = 2n^D(2^{-D} + 2\times 2^{-2D} + 3\times 2^{-3D} + \dots + (m + 1)\times 2^{-(m+1)D}) 
\end{align}
Subtract $(2)$ from $(1)$:
\begin{align*}
    (1) - (2) &= C(1 - 2^{-D}) = 2n^D(1 +  2^{-D} + 2^{-2D} + \dots + 2^{-mD} - (m + 1)\times 2^{-(m+1)D}) \\
    &= 2n^D(1 + \frac{2^{-D}}{1 - 2^{-D}} - (m + 2)\times 2^{-(m+1)D}) < \frac{2n^D}{1- 2^{-D}}
\end{align*}
So the storage cost of FMG-cycles $C$ is \(C < \frac{2n^D}{(1- 2^{-D})^2}\).\\
Let WU denote the computational cost of performing one relaxation sweep on the finest grid. The computational cost of FMG-cycles is less than $\frac{2WU}{(1- 2^{-D})^2}$.\\
\subsection*{For \(D = 1\):}
The storage cost of FMG-cycles $C$ is \(C < \frac{2n}{(1- 2^{-1})^2} = 8n\).
\subsection*{For \(D = 2\):}
The storage cost of FMG-cycles $C$ is \(C < \frac{2n^2}{(1- 2^{-2})^2} = \frac{32n^2}{9}\).
\subsection*{For \(D = 3\):}
The storage cost of FMG-cycles $C$ is \(C < \frac{2n^3}{(1- 2^{-3})^2} = \frac{128n^3}{49}\).

\section*{Exercise 9.41}
The method alternates between relaxation (smoothing) on the fine grid and correction on the coarse grid. This combination allows it to efficiently eliminate both high-frequency and low-frequency errors in the solution. Therefore, the coeficients \(c_1, c_2, c_3, c_4\) are small.
\subsection*{Plot $n = 64$}
As shown in Figure 5:
\begin{figure}
    \centering
    \includegraphics[width=0.3\linewidth]{E9_41_64.jpg}
    \caption{Exercise 9.41$(n = 64)$}
    \label{E9_41_64}
\end{figure}

\subsection*{Plot $n = 128$}
As shown in Figure 6:
\begin{figure}
    \centering
    \includegraphics[width=0.3\linewidth]{E9_41_128.jpg}
    \caption{Exercise 9.41$(n = 128)$}
    \label{E9_41_128}
\end{figure}

\section*{Exercise 9.45}
The range \( \mathcal{R}(I_h^{2h}) \) consists of all possible coarse grid vectors that can be obtained by applying \( I_h^{2h} \) to fine grid vectors. Since \( I_h^{2h} \) maps from \( \mathbb{R}^n \) to \( \mathbb{R}^{n/2} \), the maximum possible dimension of the range is \( \frac{n}{2} \).\\
However, the sum of the coarse grid values is constrained by the sum of the fine grid values. This constraint reduces the dimension of the range by 1, leading to:

\[
\dim\mathcal{R}(I_h^{2h}) = \frac{n}{2} - 1.
\]
The null space \( \mathcal{N}(I_h^{2h}) \) consists of all fine grid vectors that are mapped to the zero vector in the coarse grid and since \(\dim\mathcal{\Omega^h}=n-1 \)

\[
\dim\mathcal{N}(I_h^{2h}) = n - 1  - \dim\mathcal{R}(I_h^{2h}) = \frac{n}{2}.
\]


\end{document}